/*
 * Implementación de las funciones definidas en el archivo de cabecera
 */

#include <malloc.h>
#include <math.h>
#include "ordenamiento.h"

int* juntarVectoresOrdenados(int tamLista1, int *lista1, int tamLista2, int *lista2) {

    // Juntamos las 2 listas.
    int tamVector = tamLista1 + tamLista2;
    int *listaFusionada = malloc(sizeof(int) * tamVector);
    int offsetLista1 = 0;
    int offsetLista2 = 0;

    int indice = 0;
    int continuarMerge = 1;

    while (continuarMerge) {

        // Si ya recorrimos todo el primer vector, copiamos todo el vector 2 en el vector resultante
        if (offsetLista1 == tamLista1) {
            int p;
            for (p=indice; p<tamVector; p++) {
                listaFusionada[indice++] = lista2[offsetLista2++];
            }
            continuarMerge = 0;
        } else if (offsetLista2 == tamLista2) {
            // Si ya recorrimos todo el segundo vector, copiamos todo el vector 1 en el vector resultante
            int p;
            for (p=indice; p<tamVector; p++) {
                listaFusionada[indice++] = lista1[offsetLista1++];
            }
            continuarMerge = 0;
        } else if (lista1[offsetLista1] <= lista2[offsetLista2]) {
            // Hay elementos en los 2 vectores. Colocamos el elemento actual del vector 1
            // en el vector resultante ya que es menor.
            listaFusionada[indice++] = lista1[offsetLista1++];
        } else {
            // Hay elementos en los 2 vectores. Colocamos el elemento actual del vector 2
            // en el vector resultante ya que es menor.
            listaFusionada[indice++] = lista2[offsetLista2++];
        }

        // Si ya llenamos todo el vector resultante, terminamos, sino llenamos el siguiente.
        if (indice == tamVector) {
            continuarMerge = 0;
        }

    }

    return listaFusionada;
    
}


/*
 * Esta función es el algoritmo propio de mergesoft.
 */
int *mergesortRecursivo(int *vector, int tamVector) {

    // Si el vector es de dimension 0 o 1, entonces ya está ordenado
    if (tamVector <= 1) {
        return vector;
    }

    // El vector es de longitud mayor que 1.
    // Dividimos el vector en 2 vectores
    int elementoDivisor = floor(tamVector / 2L);
    int tamLista1 = elementoDivisor;
    int tamLista2 = tamVector - elementoDivisor;
    int *lista1 = vector;
    int *lista2 = vector + elementoDivisor;

    // Ordenamos las listas recursivamente
    int *lista1Ordenada = mergesortRecursivo(lista1, tamLista1);
    int *lista2Ordenada = mergesortRecursivo(lista2, tamLista2);

    // Juntamos las 2 listas obteniendo una sola lista ordenada
    int *vectorOrdenado = juntarVectoresOrdenados(tamLista1, lista1Ordenada, tamLista2, lista2Ordenada);

    // Liberamos la memoria ocupada por los 2 vectores, en caso de ser necesario

    if (tamLista1 > 1) {
        free(lista1Ordenada);
    }

    if (tamLista2 > 1) {
        free(lista2Ordenada);
    }

    return vectorOrdenado;

}